package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.ListNode;
import com.leetcode.common.utils.ListNodeUtils;

/**
 * @author 覃国强
 * @date 2022-07-13 17:05
 */
public class 题库_0234_回文链表 {

  public static void main(String[] args) {
    ListNode head = ListNodeUtils.generateListNode(new int[]{1, 2, 3, 4, 5, 5, 4, 3, 2, 1});
    ListNodeUtils.print(head);

    Solution solution = new Solution();
    System.out.println(solution.isPalindrome(head));
    ListNodeUtils.print(head);
  }



  static
  class Solution {
    public boolean isPalindrome(ListNode head) {

      // 链表拆分
      ListNode leftTail = getLeftTailNode(head);
      ListNode rightHead = leftTail.next;
      leftTail.next = null;

      // 反转右侧链表
      rightHead = reverseListNode(rightHead);

      // 判断链表是否为回文
      boolean answer = isPalindrome(head, rightHead);

      // 恢复链表
      rightHead = reverseListNode(rightHead);
      leftTail.next = rightHead;

      return answer;
    }

    private boolean isPalindrome(ListNode left, ListNode right) {
      while (left != null && right != null) {
        if (left.val != right.val) {
          return false;
        }
        left = left.next;
        right = right.next;
      }
      return true;
    }

    private ListNode getLeftTailNode(ListNode head) {
      ListNode slower = head;
      ListNode faster = head.next;
      while (faster != null && faster.next != null) {
        slower = slower.next;
        faster = faster.next.next;
      }
      return slower;
    }


    private ListNode reverseListNode(ListNode head) {
      ListNode prev = null;
      while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
      }
      return prev;
    }

  }

}
